Fall 2008 Seminar Series

DATE: September 11, 2008
LOCATION: E40-298
TIME: 4:15pm
Reception immediately following in the ORC ConferenceRoom, E40-106

SPEAKER:
Jesus De Loera

TITLE
Transportation Polytopes: a Twenty-year Update

ABSTRACT
A transportation polytope consists of all multidimensional arrays of nonnegative numbers that satisfy certain sum conditions on subsets of the entries. Transportation problems are among the first ever studied combinatorial optimization problems, going back to the 1930's work of Kantorovich and Koopmans. Transportation polytopes arise naturally in optimization and statistics and have also interest for pure mathematics since permutation matrices, latin squares, magic squares, appear as lattice points or vertices of these polytopes.

 

In this talk I will survey recent advances on the understanding of the geometry of these polyhedra in connection with discrete optimization. In particular, I will report on the following ``universality theorem'': Every rational convex polytope is strongly isomorphic to a 3-way, 2-margin transportation polytope. This has very interesting consequences for integer programming. I will also present new results on the problem of solving transportation problems with non-linear objective functions. If time permits, I will end with some results that pertain to the special case of assignment problems.

 

Based on various joint papers with Ed Kim, Fu Liu (UC Davis), Francisco Santos (U. Cantabria) and Shmuel Onn (Technion Haifa)